package sort;

public class HeapSort extends Sort {

    public static void main(String[] args) {
        sort = new HeapSort();
        sort.run();
    }

    @Override
    protected void sort(int[] nums, int start, int end) {
        buildHeap(nums);
        for (int i = nums.length - 1; i >= 0; i--) {
            swap(nums, 0, i);
            maxHeapify(nums, 0, i - 1);
        }
    }

    private void buildHeap(int[] nums) {
        int heapSize = nums.length - 1;
        int startIndex = nums.length / 2;
        for (int i = startIndex; i >= 0; i--) {
            maxHeapify(nums, i, heapSize);
        }
        //        for (int i = 0; i < nums.length; i++) {
        //            maxHeapify(nums,i,heapSize);
        //        }
    }

    private void maxHeapify(int[] nums, int index, int heapSize) {
        int left = index * 2;
        int right = index * 2 + 1;
        int tempIndex = index;
        if (left <= heapSize && nums[left] > nums[tempIndex]) {
            tempIndex = left;
        }
        if (right <= heapSize && nums[right] > nums[tempIndex]) {
            tempIndex = right;
        }
        swap(nums, index, tempIndex);
        if (tempIndex != index) {
            maxHeapify(nums, tempIndex, heapSize);
        }
    }
}
